package tree.treerecursion;

import tree.TreeNode;

/**
 * @Classname : BinaryTreeMaximumPathSum
 * @Description : 124. 二叉树中的最大路径和
 *
 * @Author : cty
 * @Date 2023/4/23 20:58
 */


public class BinaryTreeMaximumPathSum {

    private int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxPathSumHelper(root);
        return max;
    }

    public int maxPathSumHelper(TreeNode root) {
        if (root == null) return 0;

        int leftMax = maxPathSumHelper(root.left);
        int rightMax = maxPathSumHelper(root.right);
        // 记录一个可能的最大路径值
        max = Math.max(max, root.val + leftMax + rightMax);
        // 若以当前节点为根节点的树最单向大路径值为负值，则最终路径不经过当前子树，返回0
        return Math.max(Math.max(0, root.val + leftMax), root.val + rightMax);
    }
}
